COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file
C00003 00003	.hd206 SPRING 1978
C00008 ENDMK
C⊗;
.REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file;
.PAGE FRAME 56 HIGH 80 WIDE;
.evenleftborder ← oddleftborder ← 1000;
.area text lines 1 to 56;
.place text;
.
.MACRO  hd206 (TERM) ⊂
.BEGIN    NOFILL  TURNON "←→"
←COMPUTER SCIENCE DEPARTMENT
←STANFORD UNIVERSITY
.SKIP  
CS206  ←COMPUTING WITH SYMBOLIC EXPRESSIONS  →TERM
.TURNOFF
.END ⊃
.
.
.MACRO hw (NUMBER, DUEDATE) ⊂
.   BEGIN TURNON "←"  NOFILL
←PROBLEM SET  NUMBER
←Due  DUEDATE
.   TURNOFF END ⊃
.
.itemmac
.
.PORTION MAINPORTION
.
.hd206 SPRING 1978
.skip
.hw 1, |April 18|

	Write LISP programs for each of the functions described below.
For each program turn in the following:
.item←0
.begin nofill indent 12,12

	#.  The internal form of the program.
	#.  The corresponding external form recursive definition.
	#.  A description of how the progam works and why.
	#.  Output from test runs on a variety of input.
.end		
	Late assignments are discouraged and will not be accepted after the 
solutions appear.
.bb Function descriptions.
.item ← 0
.BEGIN INDENT 0,6

#. ⊗allsub[u,v] returns a list giving all occurrences of the list ⊗u 
as a toplevel sublist of ⊗v. An occurrence is given by the number
denoting the position in ⊗v where the match begins.
Thus  ⊗⊗⊗allsub[$$(A A),(A A A A A)$] = $$(1 2 3 4)$.⊗

#. ⊗allsub![u,v] returns a list giving all occurrences of the list ⊗u 
as a sublist of ⊗v, at any level.  Now an occurrence is a list of numbers
giving the path to beginning to sublist occurrence. 
Thus  ⊗⊗⊗allsub![$$(A),(A (B (A (B (A)))))$] = $$((1) (2 2 1) (2 2 2 2 1))$⊗

#.  ⊗mapexp takes as arguments an S-expression, a unary
function ⊗f1 and a binary function ⊗f2.  It takes the S-expression apart,
applies the unary function to each atom and puts the result back 
together using the binary function. 
Thus if ⊗f1 is the identity function and ⊗f2 is ⊗cons then ⊗maptree returns
a copy of the S-expression.  If ⊗f1 is ⊗ncons (forms a list of one element)
and ⊗f2 is ⊗append then ⊗maptree returns the ⊗fringe of the S-expression.

#.  Let a graph ⊗g be represented as described in Chapter I of the text
and suppose that whenever there is an edge from ⊗x to ⊗y  there is also 
an edge from ⊗y to ⊗x.  A component of the graph is a collection of 
vertices which are all connected to each other by edge paths but not 
connected to any vertices not in this collection.  Write a function
⊗ncomps to determine the number of components of a graph ⊗g.  

#. ⊗partition[u,n] is the list of partitions of the list ⊗u into
⊗n sublists ⊗u1, ... ⊗un such that ⊗⊗u1*[u2*...*un]=u⊗.  
If ⊗n is greater than the length of ⊗u then your program should return
an error message of some kind.
Thus 

⊗⊗⊗partition[$$(A B C),2$]=$$((A) (B C))((A B) (C)))$⊗

Write a program ⊗testpart to test the result returned by ⊗partition.  
For each partition, ⊗testpart should append together the lists ⊗ui 
and check that the result is ⊗u.  

.END